/****************************************************************************
*
*					Functions of class GreedyAlgorithm
*
****************************************************************************/

#include <string>
#include <utility>
#include <iostream>
#include <stdlib.h>
#include "SimpleFeature.h"
#include "GreedyAlgorithm.h"

// calling resize for at least this number of elements
#define minVecResize		16
#define	eps					0.000001



/****************************************************************************
*					GreedyAlgorithm::GreedyAlgorithm
*
*	Description:	Standard constructor with initialization of internal parameters
*	Parameters:		-
*	Returns:		-
*
****************************************************************************/
GreedyAlgorithm::GreedyAlgorithm (void) {
	// Initial values of parameters:
	//	max size of arbitrary features (for them to be used in the algorithm)
	maxSizeOfArbitraryFeats = 4;
	// number of iterations without change of objective function value
	numIterWithSameValue = (unsigned int) -1;
	//  max number of all features in the pgm
	maxWholeNumOfFeats = (unsigned int) -1;
	//  min acceptable gain in likelihood
	minLikelihoodGain = 1.001;
	inference = NULL;
	parameterLearning = NULL;
}


/****************************************************************************
*					GreedyAlgorithm::~GreedyAlgorithm
*
*	Description:	Standard destructor with removing all dynamic internal variables
*	Parameters:		-
*	Returns:		-
*
****************************************************************************/
GreedyAlgorithm::~GreedyAlgorithm (void) {
	if (inference != NULL)
		delete inference;
	if (parameterLearning != NULL)
		delete parameterLearning;
}


/****************************************************************************
*					GreedyAlgorithm::learn
*
*	Description:	Main Learning Procedure
*	Parameters:		-
*	Returns:		-
*
****************************************************************************/
int GreedyAlgorithm::learn (DataSet& dataSetLearn, PGMStruct& pgmStruct) {
	// Main cycle of the learning algorithm
	unsigned int numberOfFeatsInPGM;
	std::vector <unsigned int> domain, values;
	SimpleFeature* newFeature;
	unsigned int i, j, k, maxGainID;
	int addRes;
	bool choosingByEQVal, stopCrit;
	float gain, eqVal, epVal, gainMax, eqValMax, epValMax;
	float newWeight, logZ;
	std::vector < std::vector < std::pair <unsigned int, unsigned int> > > setOfAllFeats;
	std::vector <bool> isIncluded;
	std::vector <float> objFuncVals;

	getAllPossibleFeatures (setOfAllFeats, pgmStruct);
	// assuming that feature should at least have 2 variables
	isIncluded.resize(setOfAllFeats.size(), false);
	for (i = 0; i < setOfAllFeats.size(); i++)
		if (setOfAllFeats[i].size() < 2)
			isIncluded[i] = true;
	k = 0;
	numberOfFeatsInPGM = 0;
	objFuncVals.resize(maxWholeNumOfFeats, 0.0);
	std::cout << "\n";
	while (numberOfFeatsInPGM < maxWholeNumOfFeats) {
		k++; // number of times this cycle run
		// Calculating gain for each possible feature
		// To run conditional inference we first must to run unconditional variant
		inference->run(logZ, pgmStruct);
		// going through all possible features - selecting which one to add now
		gainMax = -1.0;
		eqValMax = -1.0;
		choosingByEQVal = false;
		for (i = 0; i < setOfAllFeats.size(); i++) {
			if (isIncluded[i]) // if the feature is already in the PGM
				continue;
			// running conditional inference for a current feature
			inference->run(eqVal, setOfAllFeats[i], pgmStruct);
			epVal = dataSetLearn.calculateEmpiricalProb(setOfAllFeats[i], setOfAllFeats[i].size());
			if (epVal < eps) { // gain would be infinity
				// if empirical probability of the feature is 0 - then selecting a feature with the max expected value
				if (eqVal > eqValMax) {
					maxGainID = i;
					gainMax = FLT_MAX;
					eqValMax = eqVal;
					epValMax = epVal;
					choosingByEQVal = true;
				}
			} else {
				if (choosingByEQVal) // gain of infinity - was reached earlier
					continue;
				gain = likelihoodGain (epVal, eqVal);
				if (gain > gainMax) {
					maxGainID = i;
					gainMax = gain;
					eqValMax = eqVal;
					epValMax = epVal;
				}
			}
		}
		// Checking the stop conditions
		if ((gainMax < 0.0) || (gainMax < minLikelihoodGain))
			break;
		isIncluded[maxGainID] = true;
		// Adding the selected feature to the PGM
		j = setOfAllFeats[maxGainID].size();
		domain.resize(j);
		values.resize(j);
		for (i = 0; i < j; i++) {
			domain[i] = setOfAllFeats[maxGainID][i].first;
			values[i] = setOfAllFeats[maxGainID][i].second;
		}
		newFeature = new SimpleFeature();
		newFeature->setDesiredValues(values);
		// calculating weight
		if (epValMax < eps)
			newWeight = 0.0;
		else
			newWeight = weightValue (epValMax, eqValMax);
		// actually adding a feature
		addRes = pgmStruct.addFeature(domain, newFeature, newWeight);
		if (addRes >= 0) // if the feature was added - than conunting it
			numberOfFeatsInPGM++;
		else // if the feature was not added - choosing a new one over again
			continue;
		// Running exact parameter learning (previously set weight was an approximation)
		objFuncVals[numberOfFeatsInPGM - 1] = parameterLearning->learn(dataSetLearn, pgmStruct, inference);
		
		// ptintout statistics: 
		std::cout << "\nMain cycle iteration: " << k << ", last obj-function value: " << objFuncVals[numberOfFeatsInPGM - 1] << "\t\t";
		
		// checking stop condition
		if (numberOfFeatsInPGM > numIterWithSameValue) {
			if (objFuncVals[numberOfFeatsInPGM - 1] != objFuncVals[numberOfFeatsInPGM - 1])
				continue;
			stopCrit = true;
			for (i = numberOfFeatsInPGM - numIterWithSameValue; i < (numberOfFeatsInPGM - 1); i++) 
				if  (std::abs(objFuncVals[numberOfFeatsInPGM - 1] - objFuncVals[i]) > eps) {
					stopCrit = false;
					break;
				}
			if (stopCrit)
				break;
		}
	}
	return 0;
}


/****************************************************************************
*					GreedyAlgorithm::setParameters
*
*	Description:	Set object patameters from environment
*	Parameters:		environment - a set of parameters read from config file
*	Returns:		0
*
****************************************************************************/
int GreedyAlgorithm::setParameters (Environment &environment) {
	double valD;
	int valI;
	std::string valStr;
	if (environment.getIntParamValue(valI, "MaxSizeOfArbitraryFeats") == 0)
		maxSizeOfArbitraryFeats = valI;
	if (environment.getIntParamValue(valI, "MaxWholeNumOfFeats") == 0)
		maxWholeNumOfFeats = (unsigned int) valI;
	if (environment.getIntParamValue(valI, "NumIterWithSameValue") == 0)
		numIterWithSameValue = (unsigned int) valI;
	if (environment.getDoubleParamValue(valD, "MinLikelihoodGain") == 0)
		minLikelihoodGain = valD;
	if (environment.getStringParamValue(valStr, "AlgorithmForRunningInference") == 0) {
		InferenceFactory inferenceFactory;
		inference = inferenceFactory.createObjectByName (valStr);
		inference->setParameters(environment);
	} else {
		std::cout << "\nError in GreedyAlgorithm::setParameters: cannot find specification of inference algorithm in the config file.\n";
	}
	if (environment.getStringParamValue(valStr, "AlgorithmForParameterLearning") == 0) {
		ParameterLearningFactory parameterLearningFactory;
		parameterLearning = parameterLearningFactory.createObjectByName (valStr);
		parameterLearning->setParameters(environment);
	} else {
		std::cout << "\nError in GreedyAlgorithm::setParameters: cannot find specification of an algorithm for parameters learning in the config file.\n";
	}
	return 0;
}


/****************************************************************************
*					GreedyAlgorithm::getAllPossibleFeatures
*
*	Description:	Return a vector of all possible features 
*					(with limitation set by maxSizeOfArbitraryFeats)
*	Parameters:		allFeats - a set of all possible features
*					pgmStrut - description of the PGM
*	Returns:		0
*
****************************************************************************/
int GreedyAlgorithm::getAllPossibleFeatures (std::vector < std::vector < std::pair <unsigned int, unsigned int> > >& allFeats, PGMStruct& pgmStruct) {
	unsigned int i, j, k, allFeatsSize, curSize;
	allFeatsSize = 0;
	for (i = 0; i < pgmStruct.nVars; i++){
		curSize = allFeatsSize;
		for (j = 0; j < pgmStruct.numOfValues[i]; j++) {
			if (allFeatsSize >= allFeats.size())
				allFeats.resize(allFeatsSize + minVecResize);
			allFeats[allFeatsSize].resize(1, std::make_pair<unsigned int, unsigned int>(i, j) );
			allFeatsSize++;
			for (k = 0; k < curSize; k++) {
				if (allFeats[k].size() < maxSizeOfArbitraryFeats) {
					if (allFeatsSize >= allFeats.size())
						allFeats.resize(allFeatsSize + minVecResize);
					allFeats[allFeatsSize] = allFeats[k];
					allFeats[allFeatsSize].push_back( std::make_pair<unsigned int, unsigned int>(i, j) );
					allFeatsSize++;
				}
			}
		}
	}
	allFeats.resize(allFeatsSize);
	return 0;
}
